// 4 分治策略
// 4.1 最大子数组问题

/// 找到最大子数组。
/// 找到数组 a 中，下标 low 和 hight，使得 low 和 hight 之间的元素和最大。
/// 参数：
/// a: 数组
/// low: 数组下标
/// high: 数组下标
/// 返回：
/// (low, high, sum)
/// low: 找到的数组起始下标
/// high: 找到的数组结束下标
/// sum: 数组 a 中 low 到 high 之间的元素和
pub fn find_max_subarray(a: &[i32], low: usize, high: usize) -> (usize, usize, i32) {
    if low == high {
        return (low, high, a[low]);
    }
    let mid = (low + high) / 2;
    let (left_low, left_high, left_sum) = find_max_subarray(a, low, mid);
    let (right_low, right_high, right_sum) = find_max_subarray(a, mid + 1, high);
    let (cross_low, cross_high, cross_sum) = find_max_crossing_subarray(a, low, mid, high);
    if left_sum >= right_sum && left_sum >= cross_sum {
        (left_low, left_high, left_sum)
    } else if right_sum >= left_sum && right_sum >= cross_sum {
        (right_low, right_high, right_sum)
    } else {
        (cross_low, cross_high, cross_sum)
    }
}

fn find_max_crossing_subarray(
    a: &[i32],
    low: usize,
    mid: usize,
    high: usize,
) -> (usize, usize, i32) {
    let mut left_sum = a[mid];
    let mut sum = 0;
    let mut max_left = mid;

    for i in (low..mid + 1).rev() {
        sum += a[i];
        if sum >= left_sum {
            left_sum = sum;
            max_left = i;
        }
    }

    let mut right_sum = a[mid + 1];
    sum = 0;
    let mut max_right = mid + 1;
    for i in mid + 1..high + 1 {
        sum += a[i];
        if sum >= right_sum {
            right_sum = sum;
            max_right = i;
        }
    }

    (max_left, max_right, left_sum + right_sum)
}

mod tests {
    #[test]
    fn find_max_subarray() {
        let a = [
            13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7,
        ];
        let high = a.len() - 1;
        assert_eq!(super::find_max_subarray(&a, 0, high), (7, 10, 43));
    }
}
